package 代码记录.校招笔试真题.笔试真题_2022.游卡;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author zx
 * @create 2022-09-20 19:22
 * 60%
 */
public class Test3 {
    ArrayList<TreeNode> res = new ArrayList<>();
    public ArrayList<TreeNode> findCommonAncestors2 (TreeNode root, TreeNode p, TreeNode q) {
        TreeNode flag = findCommonAncestors(root,p,q);
        preOrder(root,flag);
        return res;
    }
    private void preOrder(TreeNode root, TreeNode flag){
        if(root == null){
            return;
        }
        if(root.val == flag.val){
            return;
        }
        res.add(root);
        preOrder(root.left,flag);
        preOrder(root.right,flag);
    }
    public TreeNode findCommonAncestors(TreeNode root, TreeNode p, TreeNode q){
        if(root == null || root.val == p.val || q.val == root.val){
            return root;
        }
        TreeNode left = findCommonAncestors(root.left,p,q);
        TreeNode right = findCommonAncestors(root.right, p,q);
        if(left == null){
            return right;
        }
        if(right == null){
            return left;
        }
        return root;
    }
}

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}